// Created by WXX on 2021/11/15 10:06
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了13.13%的用户
 * 内存消耗：7.2 MB, 在所有 C++ 提交中击败了14.38%的用户
 */
class Solution {
public:
    int numTilings(int n) {
        const int MOD = 1e9 + 7;
        int w[4][4] {
                {1, 1, 1, 1},
                {0, 0, 1, 1},
                {0, 1, 0, 1},
                {1, 0, 0, 0},
        };
        vector<vector<int>> f(n + 1, vector<int>(4));
        f[0][0] = 1;
        // f[i][j] -> f[i + 1][k]
        for (int i = 0; i < n; i++)
            for (int j = 0; j < 4; j++)
                for (int k = 0; k < 4; k++)
                    f[i + 1][k] = (f[i + 1][k] + f[i][j] * w[j][k]) % MOD;
        return f[n][0];
    }
};

int main() {

    for (int i = 1; i < 10; i++)
        cout << Solution().numTilings(i) << ' ';  // 1 2 5 11 24 53 117 258 569
    cout << endl;

    return 0;
}
